COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a24.tex[154,phy] \today\hfill}

\bigskip
Proofs by induction about summations of polynomial functions, with geometrical
insights:

\figbox 2.5truein:

$2\sum↓{i=1}↑ni=n(n+1)$. Basis step is trivial. For induction step,
inspect above diagram.

$6\sum↓{i=1}↑n i↑2=n(n+1)(2n+1)$.

Below is a picture of a rectangular solid; all parts have depth $n+1$
(perpendicular to plane of the picture).

\figbox 2.5truein:

\noindent
It illustrates that
$$n(n+1)(2n+1)+6(n+1)↑2=(n+1)(n+2)(2n+3)\,,$$
and that six squares of each size up to $1\times n\times n$ can be made
into a rectangular solid of dimension
$n\times (n+1)\times (2n+1)$. Basis step is trivial, and diagram is
induction step.

\vfill\eject

The picture below shows that from $4i$ squares of dimension $i\times i$,
for each~$i$ from 1 to~$n$, one can make a square whose side is
$n(n+1)=2\sum↓{i=1}↑ni$. Basis step is trivial, and induction step is
the outer layer of the diagram.

\vfill

Given such a square, add along each side a row of $n$~squares, each of
dimension $(n+1)\times (n+1)$; then put four more such squares at the
corners to (literally) complete the square, for a total of $4(n+1)$
squares of dimension $(n+1)\times (n+1)$; this shows that
$$4\sum↓{i=1}↑ni↑3=\bigl(n(n+1)\bigr)↑2\,\bblackslug$$

\eject

\figbox 2truein:

\noindent
The picture above shows a rectangular solid of depth~$n$, height $n+1$,
and width $n+2$. By placing on it a solid of depth~3, height $n+1$,
and width $n+2$, we get a rectangular solid of height $n+1$, width
$n+2$, and depth $n+3$. This is the induction step to show
$$3\sum↓{i=1}↑ni(i+1)=n(n+1)(n+2)\,.$$
The same construction in higher dimensions shows
$$(p+1)\sum↓{i=1}↑ni(i+1)\ldots (i+p-1)=n(n+1)\cdots (n+p)\,,$$
or, using the factorial-powers notation $n↑{\overline{e}}=n(n+1)\ldots (n+e-1)$,
$$(p+1)\sum↓{i=0}↑ni↑{\overline{p}}=n↑{\overline{p+1}}\,,$$
analogous to
$$(p+1)\int↓0↑nx↑p\,dx=n↑{p+1}\,\bblackslug$$

\figbox 1.5truein:

\noindent 
The above diagram is the induction step in showing that the sum of the first
$n$~odd numbers is
$$\sum↓{i=1}↑n(2i-1)=n↑2\,.$$

\figbox 3truein:

\centerline{Depth of all parts $=2n+1$)}

\bigskip
The diagram above shows that to a rectangular solid of dimensions
$(2n-1)\times (2n)\times (2n+1)$ can be added six squares, each of dimension
$1\times (2n+1)\times (2n+1)$, to get a rectangular solid of dimensions
$(2n+1)\times (2n+2)\times (2n+3)$. This is the induction step in showing that
$$6\sum↓{i=1}↑n(2i-1)↑2=(2n-1)(2n)(2n+1)\,,$$
so that the sum of the first $n$ odd squares is
$$\sum↓{i=1}↑n(2i-1)↑2={4n↑3-n\over 3}={2n+1\choose 3}\,.$$

\bigskip\noindent
{\bf Exercise:} What is the sum of the first $n$ odd cubes?


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 16, 1984

\bye